/*  simdcvdc.cpp  by K.Tsuru  */
// function ID = 414    BRADIX
/***************************************************************************
SInteger class
BRADIX ---> DRADIX fast radix conversion
Provides the divide radix conversion.
In special case it is equivalent to the binary splitting method. See below.

[Argorithm]
step 1
For a SInteger number u[N-1]...u[1]u[0] it converts into SLong by 'd' figures
independently and puts into SLong r[].
Let B = BRADIX and assume that N=p*d. Using arithmetic of SLong(radix = DRADIX)
it evaluates
r[0]  <-- u[d-1]*B^(d-1)+...+u[1]*B+u[0]
r[1]  <-- u[2*d-1]*B^(d-1)+...+u[d+1]*B+u[d]
...........................................
r[k]  <-- u[(k+1)*d-1]*B^(d-1)+...+u[k*d+1]*B+u[kd]
...........................................
r[p-1]<-- u[d*p-1]*B^(d-1)+...+u[(p-1)*d+1]*B+u[(p-1)*d]
          =u[N-1]*B^(d-1)+...+u[N-d+1]*B+u[N-d].
In each polynomial the Horner's method can be used.

step 2
It converts into SLong binding two figures of r[].
It assumes that p = 2^n, if not chooses 'n' to satisfy 2^(n-1)< p <2^n and
fills the residual upper part of r[] with zeros.
A. Starting with Q = B^d,
B.
 B-1 r[0] <-- r[1]*Q + r[0]
     r[1] <-- r[3]*Q + r[2]
     .....................
     r[k] <-- r[2*k+1]*Q+r[2*k]
     ....................,
     r[p/2-1] <-- r[p-1]*Q+r[p-2]
 B-2 p <-- p/2
 B-3 When p = 1, go to step C. If not let Q *= Q and return to step B-1.
C. The required result is put in r[0].

If the FFT multiplication is used the computational complexity has an order
of N(logN)^2.

[Notice]
1)For the step 1 the paralell computing can be applied.
2)Taking d=1 the above method is equivalent to the binary splitting one.
******************************************************************************/
#ifndef SN_H
#include "sn.h"
#endif

SLong SInteger::DConvToDec() const {
    int N = (int)Head()+1, rsz, z;
    if(!Sign(414)) return 0.0;
    if((uint)N <= 2u*minArraySize) return NConvToDec();

    int j, k, p, q;
    double w;
    w = FFTMinSize(DEC_INT)*(double)DFIGURES/log10((double)BRADIX); // ver.2.17
    p = (int)w-1;
    rsz = N/p;
    if(N % p) rsz++;

    SLong* r = new SLong[rsz];
    w = (double)N*log10((double)BRADIX)/(double)DFIGURES + 1.0; // ver.2.17
//figures in DRADIX
//An overflow error will be detected by FigureAlloc().
    uint dec_fig = min(ceilpow2((uint)w), r[0].MaxSize());
/*
It allocates the memory of r[0],r[1] and R whose required size is previously known.
This takes into the unreducible size mode.
*/
    r[0].FigureAlloc(dec_fig, -1);
    if(rsz > 1) r[1].FigureAlloc(dec_fig/4u, -1);

    SLong R(r[0].Type(), dec_fig/2u, BRADIX);
    const fType* pf = ReadFigures();
/*
step 1 :
About the computational complexity the ratio of this step to step 2 is 1/6 to 1/5.
Then optimizing this step does not improve so much.
*/
    for(k = 0; k < rsz - 1 ; k++){  //pass if rsz == 1
        q = (k+1)*p - 1;
        r[k].SetLong(pf[q]);    // Horner's method
        for(j = q - 1; j >= k*p; j--){
            r[k] = LsMult(r[k], BRADIX);
            r[k].LsAdd(pf[j]);
//          r[k] = r[k]*R + figure(j);
        }
    }
//upper residual figures k = rsz - 1
    r[k].SetLong(pf[N-1]);  // r[k] = figure(N-1);
    for(j = N-2; j >= k*p; j--){    //When rsz = 1 and k = 0, this is executed.
        r[k] = LsMult(r[k], BRADIX);
        r[k].LsAdd(pf[j]);
    }
    if(rsz == 1) goto Ret;
/*
step 2 : It converts into SDLong binding two figures of r[].
It is fast because the FFT multiplication is used.
If much memory can be used it will be better that the table of R^n is made on
hard disk and reads it.
*/
// Here rsz >= 2.
    z = ceilpow2(rsz);
    R = Lpow(R, p);     // = BRADIX^p

    while(z){
        for(j = 0; j < z ; j += 2){
            if(j <= rsz-2) r[j/2] = r[j+1]*R + r[j];
            else if(j == rsz-1) r[j/2] = r[j];
            else r[j/2].SetZero();  // j >= rsz
        }
        z /= 2;
#if PoorMemory  // Upper parts of r[] occupy small memory, then "Out of memory" will not occur.
        for(j = z; j < s; j++) r[j].SizeZero();
        for(j = 2; j < z; j++) r[j].ReduceSize();
        if(z == 2) r[1].ReduceSize();
#endif
        if(z == 1) break;   //do not evaluate last R *= R;
        R *= R;
    }
Ret:
//The last result is put in r[0].
    R.SizeZero();
    R = r[0];
    delete[] r;

    if(Sign() < 0) R.ChangeSign();
    return R;
}